During the past years, computing devices such as computers, mobile phones, game consoles, personal digital assistants, etc., have evolved so much that a large variety of content is now consumed with these devices. Most of the content, e.g., media files, is stored in caches distributed closer to the users. As users' preferences for content change continuously and the amount occupied by the content is increasing, caches need smart replacement algorithms for updating their content. In general, a cache replacement algorithm is responsible for populating a cache and for deciding which objects stay and which ones should be removed when new objects are requested. Thus, the replacement algorithm essentially controls the functioning of the cache.
A known cache replacement algorithm is the Least Recently Used (LRU) algorithm. According to this algorithm, objects are always admitted to the cache. When the cache is full, the least recently used object is identified and deleted to make room for a new object. That is, the object that has been in the cache the longest time without being used is selected for elimination. A cache using this algorithm needs to keep track of when each object was last used.
Proxy cache servers are deployed in a network to replicate content near to the end-user. The proxy cache servers increase the performance of the network by decreasing user perceived latency, traffic congestion and the load on the content provider's servers. All these cache servers need a cache replacement algorithm.
In the past, various studies regarding replacement algorithms for proxy caches were focused on static text based objects such as Hypertext Markup Language (HTML) web pages and images. Recently, however, most of the Internet traffic originates from video and media applications. Thus, cache servers designed specifically for dealing with media streaming face several new aspects due to the higher complexity of streaming applications, as noted, for example, in Chen et al., “Adaptive and lazy segmentation based proxy caching for streaming media delivery,” Proceedings of the 13th international Workshop on NOSSDAV, Monterey, Calif., USA, (June 2003), in Chen et al., “Segment-Based Proxy Caching for Internet Streaming Media Delivery,” IEEE MultiMedia 12, 3 (July 2005) and in Wu, K., “Segment-based proxy caching of multimedia streams,” Proceedings of the 10th Intern. Conference on WWW, Hong Kong (2001).
Differently from static web objects, media streams have a large size (hundreds of megabytes to gigabytes) and therefore caching the entire object is impractical since a few objects would quickly exhaust the cache space. To address this problem, a segmentation technique of the objects has been used. Besides large file sizes, multimedia applications have to deal with a complex and longer lifespan of streaming objects, and also with guaranteeing an acceptable quality of experience.
To improve caching of media streaming content, particular algorithms for cache replacement were proposed. Some of these are (i) Adaptive and Lazy Segmentation algorithm disclosed in Chen et al., “Adaptive and lazy segmentation based proxy caching for streaming media delivery,” Proceedings of the 13th international Workshop on NOSSDAV, Monterey, Calif., USA, (June 2003), (ii) Segment-based algorithm disclosed in Wu, K., “Segment-based proxy caching of multimedia streams,” Proceedings of the 10th Intern. Conference on WWW, Hong Kong (2001) and (iii) a least recently least frequently used (LRLFU) algorithm disclosed in Satsiou et al., “Impact of Frequency-based Cache Management Polices on the Performance of Segment Based Video Caching Proxies,” Proceedings of the 3rd IFIP Networking Conference, pp. 1120-1131 (May 2004), the entire contents of these documents being incorporated by reference herein. These algorithms are based on segmentation approaches and object's popularity information, providing a better utilization of the available storage space.
Sen et al. presents in “Proxy prefix caching for multimedia streams,” Proceedings of IEEE INFOCOM'99, IEEE Computer Society (1999), a new caching algorithm called Partial Caching. This caching algorithm stores the initial segments (prefix) of the multimedia objects. When receiving a request for a specific object, the initial frames of that object, that are stored in the cache, are transmitted to the user while the cache recovers the rest (suffix) of the object (simultaneously) from a main server. This and other documents also discuss an optimal size of the prefix, and argue that prefix caching can decrease the start-up delay and reduce traffic between the server and the proxy for popular content. Similar work that proposes the idea of selective caching has been investigated by Miao and Ortega in, “Proxy Caching for Efficient Video Services over the Internet,” Proceedings of the 9th International Packet Video Workshop (1999). In this approach, not only the prefix of the object is stored but any part of it preventing possible playback delays and allowing seek operations in the stream.
Chen et al. proposes in “Segment-Based Proxy Caching for Internet Streaming Media Delivery,” IEEE MultiMedia 12, 3 (July 2005), a segment-based proxy-caching algorithm in which a streaming object is partitioned into exponential variable sized objects based on their distance from the beginning of the object. In this work, the segment size increases exponentially, i.e., the ith segment has a size 2i-1. With this approach, the cache can discard half of the cached object with a single action improving cache management. The number of segments to be cached for each object is based on the frequency of access and the segment distance from the beginning of the media. The admission policy applies different criteria for the various (beginning and later) segments of an object, based on a segment number. This technique reduces the cache-replacement granularity compared to the prefix/suffix algorithm and also achieves a better byte-hit ratio.
However, this approach has some parameters, such as the number of initial segments (Kmin) and the capacity of the cache reserved for them (Cinit), that have to be pre-configured according to workload's characteristics in order to achieve its maximum performance.
Another algorithm disclosed in Satsiou and Paterakis “Efficient caching of video content to an architecture of proxies according to a frequency-based cache management policy,” Proc. of the 2nd Intern. Workshop on Advanced Archit. and Algorithms for Internet Delivery and Applications, ACM, New York, USA (2006), proposes an algorithm aimed at capturing changes in object popularity considering both the newness and frequency of the requested object, i.e., an LRLFU approach. This scheme is based on the exponential segment-based but introduces a new policy of caching replacement by blending aspects of least recently used (LRU) and least frequently used (LFU) algorithms. It outperforms the exponential strategy in terms of byte-hit ratio and fraction of requests with delayed start but still has the same drawbacks of the pre-configured parameters (Kmin and Cinit) which need to be customized for each workload characteristics.
The Adaptive and Lazy Segmentation based caching algorithm discussed above tries to adapt the segmentation to the last user's access statistics and segments the object only after retrieving sufficient user's behavior information. This scheme includes an aggressive admission policy, a lazy segmentation approach and a two-phase iterative replacement policy. The algorithm captures the object popularity through a complex caching utility function. Although this strategy achieves high rates of byte-hit ratio, it does not perform well in terms of preventing initial start-up latency.
The Lazy strategy was extended to a peer-assisted media distribution system. In this new approach, a segment-based peer-to-peer (P2P) media system called PROP, “collaborating and coordinating PROxy and its P2P clients” is used to distribute multimedia content using the P2P overlay network and the proxy cache. While in the Lazy's proposal the priority-based function is applied at the level of objects in the proxy cache, in PROP the same priority-based function is applied at the level of segments of the P2P system.
For example, the popularity of a segment is defined by
      p    =                                        S            sum                                S            0                                    (                                    T              r                        -                          T              0                                )                    *      min      ⁢              {                  1          ,                                                                      T                  r                                -                                  T                  0                                            n                                      t              -                              T                r                                                    }              ,where t is the current time, T0 is the time when the segment is accessed for the first time, Tr is the most recent access time of the segment, Ssum is the cumulative bytes that the segment has been accessed, S0 is the size of the segment in bytes, n is the number of requests for this segment,
            S      sum              S      0            (                  T        r            -              T        0              )  represents the average access rate of a segment in the past normalized by the segment size,
  min  ⁢      {          1      ,                                                  T              r                        -                          T              0                                n                          t          -                      T            r                                }  represents the probability of the future accesses, and
            T      r        -          T      0        nis the average time interval of accesses in the past.
If
            t      -              T        r              >                            T          r                -                  T          0                    n        ,the possibility that a new request arrives is small. Similarly to Lazy's approach, the segment with the lowest value for p is chosen by the algorithm to be removed when the cache is full.
Some of the problems of the existing caching algorithms are now discussed. First, it is difficult to achieve an algorithm able to improve both byte-hit ratio and startup delay metric, providing a balanced performance for both metrics. Second, the core solutions that reduce the number of media files with delayed start require manual configuration according to the workload to achieve a good performance. The existing solutions also show that it is difficult to obtain an increase in the byte hit ratio performance.
Accordingly, it would be desirable to provide devices, systems and methods that avoid the afore-described problems and drawbacks.